home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 248_01 / quick.c < prev    next >
Text File  |  1989-08-16  |  7KB  |  316 lines
  1. /*    QUICK:    Quicksort module for MicroSPELL 1.0
  2.         Spell Checker and Corrector
  3.  
  4.         (C)opyright May 1987 by Daniel Lawrence
  5.         All Rights Reserved
  6. */
  7.  
  8. #include    <stdio.h>
  9. #include    "dopt.h"
  10. #include    "dstruct.h"
  11. #include    "ddef.h"
  12.  
  13. possort()    /* sort the current wordlist on position order */
  14.  
  15. {
  16.     int cmppos();
  17.     static WORD lastpos =        /* infinite key */
  18.         {32767, 32767, 32767, 0xFF};
  19.  
  20.     /* set comparison routines to check positions */
  21.     comp = &cmppos;
  22.  
  23.     /* make sure there is a "infinite" key at the end */
  24.     sword[numwords] = &lastpos;
  25.  
  26.     /* and sort them */
  27.     quick(0, numwords - 1);
  28. }
  29.  
  30. wordsort()    /* sort the current wordlist on word order */
  31.  
  32. {
  33.     int cmpnam();
  34.     static WORD lastalpha =        /* infinite key */
  35.         {0, 0, 0, 0xFF};
  36.     /* this is the rest of the lastalpha key....make sure it is
  37.        right after last alpha */
  38.  
  39.     /* set comparison routines to check names */
  40.     comp = &cmpnam;
  41.  
  42.     /* make sure there is a "infinite" key at the end */
  43.     sword[numwords] = &lastalpha;
  44.  
  45.     /* and sort them */
  46.     quick(0, numwords - 1);
  47. }
  48.  
  49. comsort()    /* sort the common word list alphabetically */
  50.  
  51. {
  52.     /* make sure there is a "infinite" key at the end */
  53.     cword[numfiltr] = hivalue;
  54.  
  55.     /* and sort them */
  56.     uquick(0, numfiltr - 1);
  57. }
  58.  
  59. quick(lower, upper)    /* quicksort part of the word list */
  60.  
  61. int lower;    /* lowermost element to sort */
  62. int upper;    /* uppermost element to sort */
  63.  
  64. {
  65.     int testkey;    /* key used to compare items */
  66.     int i, j;    /* quicksort partitioning pointers */
  67.     WORD *t;    /* temp pointer into word list */
  68.  
  69.     /* if we have less than 9 items...bubble sort them */
  70.     if ((upper - lower) < 9) {
  71.         slow(lower, upper);
  72.         return;
  73.     }
  74.  
  75.     /* swap the middle item for the first...*/
  76.     testkey = (upper - lower) / 2 + lower;
  77.     t = sword[testkey];
  78.     sword[testkey] = sword[lower];
  79.     sword[lower] = t;    
  80.  
  81.     /* set up the pointers and prepare to partition */
  82.     testkey = lower;
  83.     i = lower;
  84.     j = upper + 1;
  85.  
  86.     /* and partition the subfile */
  87.     while (i < j) {
  88.  
  89.         /* scan to the right */
  90.         i++;
  91.         while ((*comp)(i, testkey) < 0)
  92.             i++;
  93.  
  94.         /* scan to the left */
  95.         j--;
  96.         while ((*comp)(j, testkey) > 0)
  97.             j--;
  98.  
  99.         /* switch em if appropriate */
  100.         if (i < j) {
  101.             t = sword[i];
  102.             sword[i] = sword[j];
  103.             sword[j] = t;
  104.         }
  105.     }
  106.     /* and now swap the testkey between the two partitions */
  107.     t = sword[j];
  108.     sword[j] = sword[testkey];
  109.     sword[testkey] = t;
  110.  
  111.     /* and sort the resulting partitions */
  112.     quick(lower, j - 1);
  113.     quick(j + 1, upper);
  114. }
  115.  
  116. slow(lower, upper)    /* do a straight bubble sort on a small subfile */
  117.  
  118. int lower;    /* lower limit */
  119. int upper;    /* upper limit */
  120.  
  121. {
  122.     int i, j;    /* ptrs in sort */
  123.     WORD *t;    /* temp value for an exchange */
  124.     int swapflag;    /* was there a swap? */
  125.  
  126.     /* make sure this is needed */
  127.     if (upper <= lower)
  128.         return;
  129.  
  130.     /* sort the suckers */
  131.     for (i = upper; i > lower; i--) {
  132.         swapflag = FALSE;
  133.         for (j = lower; j < i; j++)
  134.             if ((*comp)(j, j+1) > 0) {
  135.                 swapflag = TRUE;
  136.                 t = sword[j+1];
  137.                 sword[j+1] = sword[j];
  138.                 sword[j] = t;
  139.             }
  140.         if (swapflag == FALSE)
  141.             return;
  142.     }
  143. }
  144.  
  145. int cmpnam(n1, n2)    /* compare the text of two source words */
  146.  
  147. int n1, n2;        /* pointer to words to compare */
  148.  
  149. {
  150.     return(strcmp(sword[n1]->w_text, sword[n2]->w_text));
  151. }
  152.  
  153. int cmppos(n1, n2)    /* compare the position of two source words */
  154.  
  155. int n1, n2;        /* pointer to words to compare */
  156.  
  157. {
  158.     WORD *p1, *p2;    /* ptr to the two words in question */
  159.  
  160.     /* grab the two word pointers */
  161.     p1 = sword[n1];
  162.     p2 = sword[n2];
  163.  
  164.     if (p1->w_file > p2->w_file)
  165.         return(1);
  166.  
  167.     if (p1->w_file < p2->w_file)
  168.         return(-1);
  169.  
  170.     if (p1->w_line > p2->w_line)
  171.         return(1);
  172.  
  173.     if (p1->w_line < p2->w_line)
  174.         return(-1);
  175.  
  176.     if (p1->w_col > p2->w_col)
  177.         return(1);
  178.  
  179.     if (p1->w_col < p2->w_col)
  180.         return(-1);
  181.  
  182.     return(0);
  183. }
  184.  
  185. uquick(lower, upper)    /* quicksort part of the common word list */
  186.  
  187. int lower;    /* lowermost element to sort */
  188. int upper;    /* uppermost element to sort */
  189.  
  190. {
  191.     int testkey;    /* key used to compare items */
  192.     int i, j;    /* quicksort partitioning pointers */
  193.     char *t;    /* temp pointer into common word list */
  194.  
  195.     /* if we have less than 9 items...bubble sort them */
  196.     if ((upper - lower) < 9) {
  197.         uslow(lower, upper);
  198.         return;
  199.     }
  200.  
  201.     /* swap the middle item for the first...*/
  202.     testkey = (upper - lower) / 2 + lower;
  203.     t = cword[testkey];
  204.     cword[testkey] = cword[lower];
  205.     cword[lower] = t;    
  206.  
  207.     /* set up the pointers and prepare to partition */
  208.     testkey = lower;
  209.     i = lower;
  210.     j = upper + 1;
  211.  
  212.     /* and partition the subfile */
  213.     while (i < j) {
  214.  
  215.         /* scan to the right */
  216.         i++;
  217.         while (strcmp(cword[i], cword[testkey]) < 0)
  218.             i++;
  219.  
  220.         /* scan to the left */
  221.         j--;
  222.         while (strcmp(cword[j], cword[testkey]) > 0)
  223.             j--;
  224.  
  225.         /* switch em if appropriate */
  226.         if (i < j) {
  227.             t = cword[i];
  228.             cword[i] = cword[j];
  229.             cword[j] = t;
  230.         }
  231.     }
  232.     /* and now swap the testkey between the two partitions */
  233.     t = cword[j];
  234.     cword[j] = cword[testkey];
  235.     cword[testkey] = t;
  236.  
  237.     /* and sort the resulting partitions */
  238.     uquick(lower, j - 1);
  239.     uquick(j + 1, upper);
  240. }
  241.  
  242. uslow(lower, upper)    /* do a straight bubble sort on a small subfile */
  243.  
  244. int lower;    /* lower limit */
  245. int upper;    /* upper limit */
  246.  
  247. {
  248.     int i, j;    /* ptrs in sort */
  249.     char *t;    /* temp value for an exchange */
  250.     int swapflag;    /* did a swap occur? */
  251.  
  252.     /* make sure this is needed */
  253.     if (upper <= lower)
  254.         return;
  255.  
  256.     /* sort the suckers */
  257.     for (i = upper; i > lower; i--) {
  258.         swapflag = FALSE;
  259.         for (j = lower; j < i; j++)
  260.             if (strcmp(cword[j], cword[j+1]) > 0) {
  261.                 swapflag = TRUE;
  262.                 t = cword[j+1];
  263.                 cword[j+1] = cword[j];
  264.                 cword[j] = t;
  265.             }
  266.         if (swapflag == FALSE)
  267.             return;
  268.     }
  269. }
  270.  
  271. #if    EBCDIC
  272. /*    if we are using the EBCDIC character set, spell, to operate
  273.     properly in regards to uppercase words in the merge() phase
  274.     MUST have uppercase sort higher then lower. To effect this,
  275.     we slip in the replacement to the library strcmp() function.
  276. */
  277.  
  278. strcmp(s, t)
  279.  
  280. char *s, *t;    /* two strings to compare with reversed case */
  281.  
  282. {
  283.     register char s1, t1;    /* current chars in s and t */
  284.     register int cresult;    /* result of current copmparison */
  285.  
  286.     /* scan through the strings */
  287.     while (*s) {
  288.         /* record the current characters */
  289.         s1 = *s;
  290.         t1 = *t;
  291.  
  292.         /* swap the case on them */
  293.         if (isletter(s1))
  294.             s1 ^= 0x40;
  295.         if (isletter(t1))
  296.             t1 ^= 0x40;
  297.  
  298.         /* compare them and return value if unequal */
  299.         cresult = s1 - t1;
  300.         if (cresult != 0)
  301.             return(cresult);
  302.  
  303.         /* advance to the next charector */
  304.         ++s;
  305.         ++t;
  306.     }
  307.  
  308.     /* if there is anything left of t it is greater */
  309.     if (*t)
  310.         return(-1);
  311.  
  312.     /* they are the same! */
  313.     return(0);
  314. }
  315. #endif
  316.